package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/2/7 15:53
 * @Version 1.0
 **/
public class FindModeInBinarySearchTree {
    private HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    int Max = Integer.MIN_VALUE;
    public int[] findMode(TreeNode root) {

        getMode(root);
        ArrayList<Integer> list = new ArrayList<>();
        for (Integer integer : map.keySet()) {
            if (map.get(integer) == Max) {
                list.add(integer);
            }
        }
        int len = list.size();
        int[] result = new int[len];
        int k = 0;
        for (Integer integer : list) {
            result[k++] = integer;
        }
        list = null;
        map = null;
        return  result;
    }

    private void getMode(TreeNode root) {
        if (root != null) {
            Integer orDefault = map.getOrDefault(root.val, 0);
            if (orDefault + 1 > Max) {
                Max = orDefault+1;
            }
            map.put(root.val,orDefault+1);
            getMode(root.left);
            getMode(root.right);
        }
    }

}
